The present invention relates generally to optical communications, and more particularly to a 2-step-optimization procedure for routing and wavelength assignment with combined dedicated shared protections in multi-cable multi-fiber optical WDM networks.
With advance modulation schemes, each channel in optical WDM networks can support several hundred gigabits or more per second data rate. Any failure in such high capacity networks can cause large amounts of data and revenue losses. Thus, in order to meet the service level agreement to end users, provisioning survivability is an essential requirement in optical WDM networks. Failure of an optical channel is mainly caused by either a transponder failure or a fiber cable cut. Survivability to a transponder failure can be provisioned by deploying redundant transponders that are referred to as backup transponders at end nodes. Survivability to a fiber cable cut can be provisioned by allocating redundant channel resources along fiber cable-disjoint routes, where one of the routes is referred to as a working route and the others are referred to as backup routes. In order to minimize the channel switching time in case of a failure, data can simultaneously be transferred on both working and backup routes by allocating dedicated resources. Such protection mechanism is referred to as the 1+1 dedicated protection. While provisioning survivability through 1+1 dedicated protection, the required number of wavelengths in the network is increased by at least the factor of the number of 1+1 dedicated protection routes requested by a traffic demand, and that cannot be used to support other network traffic. Thus, as the requested number of 1+1 dedicated protection routes increases, survivability of the traffic demand increases; however, the wavelength utilization decreases.
It is noted here that the term “fiber cable” (or simply “cable”) refers to the physical bundle of fibers within the same assembly, this is also called “fiber trunk” sometimes. Each cable can contain multiple optical fibers or just a single optical fiber. If they are n fibers between two optical network nodes, these fibers can be contained within the same fiber cable, or they can be distributed among n cables containing 1 fiber each, or they can be distributed among m cables where 1≦m≦n. Once a fiber cable is cut, all the fibers contained within the cable are disconnected, but other cables might not be affected.
Wavelength resource utilization can be improved if backup wavelengths along backup routes can be shared among multiple working connections that are routed on fiber cable-disjoint routes. Such protection mechanism is referred to as shared protection. Contrarily, the connection switching time in the shared protection mechanism is increased by the port switching time and signal propagation time between end users than that of the 1+1 dedicated protection mechanism.
The survivability of time-critical applications can be increased in an efficient manner by provisioning a traffic demand with combined 1+1 dedicated and shared protections. The survivability of a traffic demand is improved exponentially with the number of total protection routes and the number of transponders, given the assumption that a failure of each fiber cable and a failure of each transponder are independent. For this invention, applicants investigate an efficient method that addresses the routing and wavelength assignment problem that provisions survivability through combined dedicated and shared protection mechanism in multi-cable multi-fiber optical WDM networks for the first time. The problem is defined as follows.
We are given a network topology G(V, E), where V is a set of nodes and E is a set of edges. Nodes i and j are connected through Fij number of fiber cables. Let fijp denotes the number of fibers confined within pth fiber cable connecting nodes i and j. We need to establish a set of traffic demands A in the network, where a traffic demand R(s, d, x, y) is requesting a working live-connection, x number of 1+1 dedicated backup live-connections, and y number of shared backup connections between source s and destination d. For each traffic demand, x+1 number of dedicated transponders are provisioned at end nodes to support working and x number of 1+1 dedicated live-connections. The released transponder due to any failure of a live-connection can be used to establish a new backup live-connection along one of the shared backup connections. Thus, in case of failures of l live-connections, if l≦y, the network can guarantee x+1 number of live-connections for a given traffic demand, otherwise, the network can support (x+1+y−l) number of live-connections. We need to find working, 1+1 dedicated backup, and shared connections, routing of these connections over physical topology, and operating wavelength of each connection such that wavelength utilization of the network is maximized. The network is transparent, and does not have traffic grooming or wavelength conversion capabilities. We refer to this problem as routing and wavelength assignment with combined dedicated and shared protections in multi-cable multi-fiber optical WDM networks.
It is noted that a “connection” represents the reserved wavelength resources along the route. A “live-connection” represents a connection with live data transfers. A wavelength in a fiber cable is referred to as a wavelength link.
So far, there is no existing solution for the routing and wavelength assignment problem with variable number of 1+1 dedicated and shared connections in multi-cable multi-fiber WDM networks. Applicants are the first to propose an efficient procedure to solve it.
If one restricts x=0 and y=0, the problem is transformed into the conventional routing and wavelength assignment problem in multi-fiber WDM networks. When x=1 and y=0, the problem is transformed into routing and wavelength assignment with 1+1 dedicated path protection. On the other hand, when x=0, and y=1, the problem is transformed into routing and wavelength assignment with shared path protection.
In another work, there was proposed a routing and wavelength assignment procedure when x=1 and y=1. The addressed problem has an additional constraint that was found working, 1+1 dedicated, and shared connections must be not only link-disjoint but also node-disjoint. In another prior work, the authors propose routing and wavelength assignment procedure when x=2, y=0, and x=0, y=2. In both these prior works, the problem was formulated using an Integer Linear Programming (ILP). The required time to solve the problem using the proposed methods increases exponentially with the input size, and thus, the proposed ILP formulations are not realistic approaches to address the problem in real time.
So far, the above mentioned prior works address the specific sub-problems of the problem addresses. Furthermore, the proposed solutions address only the case when each fiber is confined within a separate fiber cable, and do not applicable for the any other distribution of fibers within fiber cables.
Accordingly, there is a need for a 2-step-optimization procedure for routing and wavelength assignment with combined dedicated shared protections in multi-cable multi-fiber optical WDM networks.